
\section{Proof of Lemma~\ref{lem:graphsize}}\label{appendix:graph_size_proof}
%\begin{proof}[Proof of Lemma~\ref{lem:graphsize}]

It follows from the construction of $\graph$ in Section~\ref{subsec:graph_description} that the number of nodes in each path $\cP^i$ is
$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa)$ (cf. Eq.~\eqref{eq:sum_phi'}).
%
\note{The real value is between $2\Lambda^\kappa$ and $2(\Lambda^\kappa+\Lambda^{\lfloor\kappa\rfloor})$}
%
Since there are $\Gamma$ paths, the number of nodes in all paths is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%
Each highway $\cH^i$ has $2\lceil\kappa\rceil\Lambda^i+1$ nodes. Therefore, there are $\sum_{i=1}^{\lfloor\kappa\rfloor} (2\lceil\kappa\rceil\Lambda^i+1)$ nodes in the highways. For $\Lambda\geq 2$, the last quantity is $\Theta(\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor})$.
%
Hence, the total number of nodes is $\Theta(\Gamma\kappa\Lambda^\kappa)$.

To analyze the diameter of $\graph$, observe that each node on any path $\cP^i$ can reach a node in highway $\cH^{\lfloor\kappa\rfloor}$ by traveling through $O(\kappa\Lambda)$ nodes in $\cP^i$. Moreover, any node in highway $\cH^i$ can reach a node in highway $\cH^{i-1}$ by traveling trough $O(\Lambda)$ nodes in $\cH^i$. Finally, there are $O(\kappa\Lambda)$ nodes in $\cH^1$. Therefore, every node can reach any other node in $O(\kappa\Lambda)$ steps by traveling through $\cH^1$. Note that this upper bound is tight since the distance between $s$ and $t$ is $\Omega(\kappa\Lambda)$.
%\end{proof}

\section{Proof of Claim~\ref{claim:highprob}}\label{app:proof_of_claim}

%\begin{proof}
Let $P^*$ be the path consisting of nodes $s^{1, f_A(1)}_1$, $\ldots$, $s^{1, f_A(1)}_L$, $t^{1, f_B(f_A(1))}_1$, $\ldots$, $t^{1, f_B(f_A(1))}_L$, $s^{1, f_A(f_B(f_A(1)))}_1$, $\ldots$, $s^{i, g^{2i-1}(f_A, f_B)}_L$, $t^{i, g^{2i}(f_A, f_B)}_1$, $\ldots$, $t^{r, g^{2r}(f_A, f_B)}_L$. We claim that the random walk will follow path $P^*$ with probability at least $2/3$. The node of distance $(2rL-1)$ from $s^{1, f_A(1)}_1$ in this path is $t^{r, g^{2r}(f_A, f_B)}_L=t^{r, \PC^{r, m}(1)}_L$ and thus the algorithm described above will output $\PC^{r, m}(1)$ with probability at least $2/3$.

To prove the above claim, consider any node $u$ in path $P^*$. Let $u'$ and $u''$ be the node before and after $u$ in $P^*$, respectively. Let $m'$ and $m''$ be the number of multiedges $(u, u')$ and $(u, u'')$, respectively. Observe that $m''\geq 6\Gamma \ell m'$. Moreover, observe that there are at most $\Gamma$ edges between $u$ and other nodes. Thus, if a random walk is at $u$, it will continue to $u''$ with probability at least $1-\frac{1}{3\ell}$. By union bound, the probability that a random walk will follow $P^*$ is at least $1-\frac{1}{3}$, as claimed.
%\end{proof}